/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Solitudefire
 * Date: 2022-08-17
 * Time: 14:44
 */
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node(int val) {
        this.val = val;
    }
}

public class BinarySearchTree {
    public Node root = null;

    /**
     * 我写的
     *
     * @param root
     * @param key
     * @return
     */
    public Node search(Node root, int key) {
        if (root.val == key) {
            return root;
        }
        if (key > root.val) {
            search(root.right, key);
        }
        if (key < root.val) {
            search(root.left, key);
        }
        return null;
    }

    /**
     * 博哥写的
     *
     * @param key
     * @return
     */
    public Node search1(int key) {
        Node cur = root;
        while (cur != null) {
            if (cur.val < key) {
                cur = cur.right;
            } else if (cur.val == key) {
                return cur;
            } else {
                cur = cur.left;
            }
        }
        return null;//没有这个数据
    }

    /**
     * 我写的
     *
     * @param val
     * @return
     */
    public boolean insert(int val) {
        if (root == null) {
            root = new Node(val);
            return true;
        }
        Node cur = root;
        Node pre = null;
        while (cur != null) {
            if (val > cur.val) {
                pre = cur;
                cur = cur.right;
            } else if (val == cur.val) {
                System.out.println("查找树中已经存有该值，插入失败");
                return false;
            } else {
                pre = cur;
                cur = cur.left;
            }
        }
        if (pre.val > val) {
            pre.left = new Node(val);
        } else {
            pre.right = new Node(val);
        }
        return true;
    }

    /**
     * 博哥写的
     *
     * @param val
     * @return
     */
    public boolean insert1(int val) {
        if (root == null) {
            root = new Node(val);
            return true;
        }

        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val == val) {
                return false;//不能有相同的数据
            } else {
                parent = cur;
                cur = cur.left;
            }
        }
        Node node = new Node(val);
        if (parent.val < val) {
            parent.right = node;
        } else {
            parent.left = node;
        }
        return true;
    }

    public void remove(int key) {
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if (cur.val == key) {
                //这里开始删除
                removeNode(cur, parent);
                break;
            } else if (cur.val < key) {
                parent = cur;
                cur = cur.right;
            } else {
                parent = cur;
                cur = cur.left;
            }
        }
    }

    public void removeNode(Node cur, Node parent) {
        if (cur.left == null) {
            if (cur == root) {
                root = cur.right;
            } else if (cur == parent.left) {
                parent.left = cur.right;
            } else {
                parent.right = cur.right;
            }
        } else if (cur.right == null) {
            if (cur == root) {
                root = cur.left;
            } else if (cur == parent.left) {
                parent.left = cur.left;
            } else {
                parent.right = cur.left;
            }
        } else {
            Node shp = cur;
            Node sh = cur.right;
            while (sh.left != null) {
                shp = sh;
                sh = sh.left;
            }
            cur.val = sh.val;
            if (sh == shp.left) {
                shp.left = sh.right;
            } else {
                shp.right = sh.right;
            }
        }
    }

    public void inOrder(Node root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }


    public static void main(String[] args) {
        int[] array = {10, 8, 19, 3, 9, 4, 7};
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        for (int i = 0; i < array.length; i++) {
            binarySearchTree.insert(array[i]);
        }
        binarySearchTree.inOrder(binarySearchTree.root);
        System.out.println("插入重复的数据");
        System.out.println(binarySearchTree.insert(3));
        System.out.println("删除数据：");
        binarySearchTree.remove(7);
        System.out.println();
        binarySearchTree.inOrder(binarySearchTree.root);
    }
}
